\documentclass[12pt]{amsart}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{macros-article}
%\usepackage{fullpage}
\usepackage[all]{xy}
\usepackage{color}
\title{The Generalized Alon Conjecture}
\date{}
\begin{document}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminaries}

The min-max theorem allows us to use Rayleigh quotients to control eigenvalues of finitely dimensional vector spaces.

\begin{theorem}[Min-Max Principle]
Let \( A \in \mathbb{M}_n(\mathbb{R}) \) be a \( n \) by \( n \) symmetric real matrix with eigenvalues \( \lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n \), then for any \( k = 1, \ldots, n \) we have that
\begin{align*}
\lambda_k &= \max \{ \min \{ \Rayleigh{A}{x} \mid x \in U \text{ and } x \neq 0 \} \mid \dim(U)=k \}\\
\intertext{and}
\lambda_k &= \min \{ \max \{ \Rayleigh{A}{x} \mid x \in U \text{ and } x \neq 0 \} \mid \dim(U)=n-k+1 \}
\end{align*}
where \( \Rayleigh{A}{x} \) is the Rayleigh quotient of the vector \( x \) and is defined by
\[
\Rayleigh{A}{x} = \frac{(Ax,x)}{(x,x)}
\]
where \( (x,y) \) denotes the standard scalar product of the vectors \( x \) and \( y \).
\end{theorem}
\begin{proof}
Since the matrix \( A \) is symmetric it is diagonalizable and we can choose an orthonormal basis of eigenvectors \( \{u_1,\ldots,u_n\} \) that is, \( u_i \) is an eigenvector for the eigenvalue \( \lambda_i \) such that \( (u_i, u_i)=1 \) and \( (u_i, u_j) = 0 \) for all \( i \neq j \).

If \( U \) is a subspace of dimension \( k \) then its intersection with the subspace
\( \text{span}\{ u_k, \ldots, u_n \} \) isn't zero (by simply checking dimensions) and hence there exists a vector \( v \) in this intersection that we can write as
\[
v = \sum_{i=k}^n \alpha_i u_i
\]
and whose Rayleigh quotient is
\[
\Rayleigh{A}{v} = \frac{\sum_{i=k}^n \lambda_i \alpha_i^2}{\sum_{i=k}^n \alpha_i^2} \leq \lambda_k
\]
and hence
\[
\min \{ \Rayleigh{A}{v} \mid x \in U \} \leq \lambda_k
\]
And we can conclude that 
\[
\max \{ \min \{ \Rayleigh{A}{v} \mid x \in U \text{ and } x \neq 0 \} \mid \dim(U)=k \} \leq \lambda_k
\]
And since that maximum value is achieved for
\[
U = \text{span}\{u_1,\ldots,u_k\}
\]
We can conclude the equality.

In the case where \( U \) is a subspace of dimension \( n-k+1 \), we proceed in a similar fashion: Consider the subspace of dimension \( k \)
\[
\text{span}\{ u_1, \ldots, u_k \}
\]
Its intersection with the subspace \( U \) isn't zero (by simply checking dimensions) and hence there exists a nonzero vector \( v \) in this intersection that we can write as
\[
v = \sum_{i=1}^k \alpha_i u_i
\]
and whose Rayleigh quotient is
\[
\Rayleigh{A}{v} = \frac{\sum_{i=1}^k \lambda_i \alpha_i^2}{\sum_{i=1}^k \alpha_i^2} \geq \lambda_k
\]
and hence
\[
\max \{ \Rayleigh{A}{x} \mid x \in U \} \geq \lambda_k
\]
And we can conclude that 
\[
\min \{ \max \{ \Rayleigh{A}{x} \mid x \in U \text{ and } x \neq 0 \} \mid \dim(U)=n-k+1 \} \geq \lambda_k
\]
And since that minimum value is achieved for \( U = \text{span}\{u_k,\ldots,u_n\} \) We can conclude the equality.
\end{proof}

\begin{lemma}
Using the same notation as in the Min-Max Principle, if \( u \) and \( v \) are nonzero orthogonal vectors such that the vector \( Au \) is orthogonal to the vector \( v \), then
\[
\lambda_2 \geq \min \{ \Rayleigh{A}{u}, \Rayleigh{A}{v} \}
\]
\end{lemma}
\begin{proof}
Denote by \( \mu \) the minimum on the right-hand-side of the above inequality. Since the matrix \( A \) is symmetric, the vector \( Av \) is also orthogonal to the vector \( u \) and so if \( w = \alpha u + \beta v \) is any vector in the span of \( u \) and \( v \) then we have
\begin{align*}
\Rayleigh{A}{w} &= \frac{(A(\alpha u + \beta v), \alpha u + \beta v)}{(\alpha u + \beta v, \alpha u + \beta v)} = \frac{\alpha^2 (Au,u) + \beta^2 (Av,v)}{\alpha^2(u,u) + \beta^2(v,v)}\\
&\geq \frac{\alpha^2 \mu (u,u) + \beta^2 \mu (v,v)}{\alpha^2(u,u) + \beta^2(v,v)} = \mu
\end{align*}
The min-max principle now guarantees that \( \lambda_2 \geq \mu \) since \( \mu \) is a lower bound on the Rayleigh quotient of any pair of vectors of a two-dimensional subspace.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Tangles}
In this section, we describe an obstruction to the Alon Conjecture.

\begin{definition}
Let \( \psi \) be a connected graph with maximal degree at most \( d \geq 3 \). Denote by \( \Tree_d(\psi) \) the universal cover of the category of \( d \)-regular graphs containing \( \psi \) as a subgraph.
\end{definition}

\begin{theorem}[Old 4.2]
Fix \( d \geq 3 \) and a graph \( \psi \). Denote by \( \rho(\psi) \) the spectral radius of \( \Tree_d(\psi) \). Any graph \( G \in \Gnd \) containing \( \psi \) as a subgraph satisfies
\[
\lambda_2(G) \geq \rho(\psi) - o_n(1)
\]
Or equivalently, for any \( \epsilon > 0 \) any graph \( G \in \Gnd \) containing \( \psi \) as a subgraph satisfies
\[
\lambda_2(G) > \rho(\psi) - \epsilon
\]
for any \( n \) large enough.
\end{theorem}
\begin{proof}

\end{proof}












\end{document}